首先,我们得知道过原点与两点的抛物线解析式:
设该函数解析式为 且过 三点。
由函数过 得 。
An Ac a day, keeps the doctor away!
首先,我们得知道过原点与两点的抛物线解析式:
设该函数解析式为 y=ax2+bx+c(a<0)且过 (0,0),(x1,y1),(x2,y2) 三点。
由函数过 (0,0) 得 c=0。
对于每个位置 i , 我们向 pi 连一条边。 结合题意可知,一个合法的排列,是一个由 n 个自环组成的图。
但现在会形成多个环,不妨记环的数量为 k , 第 i 个环的大小为 si(包括自环)。
我们现在要做的,就是将这 k 个环拆成 n 个自环。
这道题用后缀自动机可以暴力解决。
建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 , 我们就可以在 DAWG 上 dp 。 dp[u]表示包含转移u的子串数量,很容易列出转移式:
一道后缀自动机的板题。
我们从根结点开始匹配,如果有转移就将cnt++
不然就顺着后缀链接向上跳,直到找到有转移的点,用 Maxlen 继续匹配。(后缀链接一定是它的子串,也能被匹配)。
这道题用后缀自动机可以暴力解决。
建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 , 我们就可以在 DAWG 上 dp 。 dp[u]表示包含转移u的子串数量,很容易列出转移式:
不难发现到f[i]就是长度为 i 子串的 ∣endpos∣ 的最大值。
根据一个性质后缀自动机的一个点的 endpos 被他的后继分为了很多部分,所以我们可以用parent树dp,处理出它的∣endpos∣。
接着是统计答案,显然我们可以用线段树覆盖。
这道题像我这样的 dp 蒟蒻都能一眼看出 dp 式:
设 sum 为 c 的前缀和,则有